package learn.sort.quick;

import learn.CommUtil;

import java.util.Arrays;


public class QuickSort {

    public static void main(String[] args) {
        int[] arr = CommUtil.arr(15);
        int[] old = Arrays.copyOf(arr, arr.length);
//        int[] arr = {69, 26};
        CommUtil.printArray("原数组: ", arr);
//        netherlandsFlag(arr, arr[arr.length - 1]);
        process2(arr, 0, arr.length - 1);
        CommUtil.printArray("排序后: ", arr);

        CommUtil.check(old, arr);
    }

    /**
     * 给定一个数组arr, 和一个整数num,把<=num的数放在数组左边,>num的放在数组右边
     */
    public static void process(int[] arr, int num) {

        int less = -1;

        for (int i = 0; i < arr.length; i++) {
            if (arr[i] <= num) {
                //交互位置
                CommUtil.swap(arr, less + 1, i);
                less++;
            }
        }
    }

    /**
     * 荷兰国旗问题
     */
    public static void netherlandsFlag(int[] arr, int num) {

        int less = -1;
        int more = arr.length;
        int i = 0;
        while (i < more) {
            if (arr[i] < num) {
                //交互位置
                CommUtil.swap(arr, less + 1, i);
                less++;
                //移动指针
                i++;
            } else if (arr[i] == num) {
                //移动指针
                i++;
            } else {
                //交互位置
                CommUtil.swap(arr, more - 1, i);
                more--;
            }
        }
    }

    /**
     *
     *
     * @param arr
     * @param l
     * @param r
     * @return ==区域的左右边界
     */
    public static int[] partition(int[] arr, int l, int r) {
        if (l == r) {
            return new int[]{l, r};
        }
        if (l > r) {
            return new int[]{-1, -1};
        }
        int less = l - 1;
        int more = r;
        int i = l;
        int num = arr[r];
        while (i < more) {
            if (arr[i] < num) {
                //交互位置
                CommUtil.swap(arr, ++less, i++);
            } else if (arr[i] == num) {
                //移动指针
                i++;
            } else {
                //交互位置
                CommUtil.swap(arr, --more, i);
            }
        }
        CommUtil.swap(arr, more, r);
        if ((less + 1) > more) {
            System.out.println("l > r");
        }
        return new int[]{less + 1, more};
    }

    /**
     * 快排 2.0
     *
     * @param arr
     */
    public static void process1(int[] arr, int l, int r) {

        if (l >= r) {
            return;
        }
        int[] ints = partition(arr, l, r);
        process1(arr, l, ints[0] - 1);
        process1(arr, ints[1] + 1, r);
    }


    /**
     * 快排 3.0 (随机快排)
     *  随机选中一个数 r,遍历数组,把数组分为3个分区:[<r区] [=r区] [>r区], [<r区] 和 [>r区] 继续左右递归分,直到区域内只有一个数,此时已完成排序
     * @param arr
     */
    public static void process2(int[] arr, int l, int r) {

        if (l >= r) {
            return;
        }
        //1.取一个随机数作为计数
        CommUtil.swap(arr, r, l + (int) (Math.random() * (r - l + 1)));
        //2.分区,返回[=r区]的左右边界
        int[] ints = partition(arr, l, r);
        //3.左边继续递归分
        process2(arr, l, ints[0] - 1);
        //4.右边继续递归分
        process2(arr, ints[1] + 1, r);
    }


}


